package algorithm.leetcode.I201to400;

import java.util.Arrays;

public class Q322 {

    public int coinChange(int[] coins, int amount) {
        // 例如coins=[1,3,7],amount=55
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, -1);
        dp[0] = 0;
        // 初始化dp数组前端
        // dp=[0,1,_,1,_,_,_,1]
        for (int coin : coins) {
            if (coin < amount) dp[coin] = 1;
        }
        // 开始递推,dp[k]=min{dp[k-coin1],dp[k-coin2],...,dp[k-coinn]}+1
        // 前提是k-coini>=0并且dp[k-coini]不是-1
        for (int i = 1; i <= amount; i++) {
            // 如果这个位置是_
            if (dp[i] == -1) {
                int temp = Integer.MAX_VALUE; // 这个位置初始值是-1
                // 尝试每个硬币
                for (int coin : coins) {
                    // 这一行是核心
                    if (i-coin >= 0 && dp[i-coin] >= 0) temp = Math.min(dp[i-coin]+1, temp);
                }
                dp[i] = temp == Integer.MAX_VALUE ? -1 : temp;
            }
        }
        return dp[amount];
    }

    public static void main(String[] args) {
        Q322 q322 = new Q322();
        int[] coins = new int[]{1,2144};
        int amount = 2;
        System.out.println(q322.coinChange(coins, amount));
    }
}
